// 给定一个只包含(),{},[]的字符串s，判断字符串括号是否匹配

// 思路：括号匹配是栈的经典应用
// 1. 判断长度是否为偶数
// 2. 使用栈来保存未匹配的左括号
//    如果遇到左括号，入栈
//    如果是右括号，看看栈顶元素与当前右括号是否是相同类型
//       如果是相同类型，令其出栈
//       如果不是，则返回false
// 3. 遍历完，判断栈是否为空，如果为空返回true，否则返回false

// 时间复杂度：O(n)
// 空间复杂度：O(1)
const Stack  = require('../../1. 堆栈基础/1. 堆栈的顺序存储实现')

function isValid(str) {
    if (str.length % 2 === 1) {
        return false
    }
    const stack = new Stack()
    for (let i = 0; i < str.length; i++) {
        if (['(', '{', '['].includes(str[i])) {
            stack.push(str[i])
        } else if (str[i] === ')') {
            if (stack.peek() === '(') {
                stack.pop()
            } else {
                return false
            }
        } else if (str[i] === '}') {
            if (stack.peek() === '{') {
                stack.pop()
            } else {
                return false
            }
        } else if (str[i] === ']') {
            if (stack.peek() === '[') {
                stack.pop()
            } else {
                return false
            }
        } 
    }
    if (stack.top === -1) {
        return true
    } else {
        return false
    }
}

let str = '{[({})]}{'
console.log(isValid(str));
